package com.cheung.leetcode.day;

import org.junit.jupiter.api.Test;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @BelongsProject : java-leetcode
 * @BelongsPackage : com.cheung.leetcode.day
 * @Author :  cheungming
 * @CreateTime : 2024-06-25 10:47:28
 * @Description : 日常练习
 * @Version : 1.0
 */
public class Code2732Test {

    public List<Integer> goodSubsetOfBinaryMatrix(int[][] grid) {
        // 假设好子集是一行，则列之和小于等于[1/2]=0,因此每个元素都为0
        // 假设好子集是两行，则列之和小于等于于[2/2]=1,因此每一列只能出现1个1，即AND为0
        // 假设好子集是三行，则列之和小于等于[3/2]=1,因此每一列只能出现1个1，即AND为0，同2行
        // 假设好子集大于等于4行，则列之和小于等于[4/2]=2,则每一列的任意两行AND都不0，否则可以退化到2行
        // 假设好子集为k行，则列之和小于等于 k/2, n行总和小于k*n/2,则每一行的平均值为n/2,因此必有一行的和大于等于n/2
        // 而且n是1~5，如果n<=3, n/2=1,则说明有一行的值大于等于1，不妨假设是第1行第1列，根据性质第一列的值为k了，矛盾
        // 如果n<=5,n/2=2,
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < grid.length; i++) {
            int mask = 0;
            for (int j = 0; j < grid[i].length; j++) {
                mask |= grid[i][j] << j;
            }
            if (mask == 0) {
                return List.of(i);
            }
            map.put(mask, i);
        }

        for (Map.Entry<Integer, Integer> e1 : map.entrySet()) {
            for (Map.Entry<Integer, Integer> e2 : map.entrySet()) {
                if ((e1.getKey() & e2.getKey()) == 0) {
                    if (e1.getValue() > e2.getValue()) {
                        return List.of(e2.getValue(), e1.getValue());
                    } else {
                        return List.of(e1.getValue(), e2.getValue());
                    }
                }
            }
        }

        return List.of();
    }

    @Test
    public void test1() {
        int[][] grid = {{0, 1, 1, 0}, {0, 0, 0, 1}, {1, 1, 1, 1}};
        assert goodSubsetOfBinaryMatrix(grid).equals(List.of(0, 1));
    }

    @Test
    public void test2() {
        int[][] grid = {{0}};
        assert goodSubsetOfBinaryMatrix(grid).equals(List.of(0));
    }

    @Test
    public void test3() {
        int[][] grid = {{1, 1, 1}, {1, 1, 1}};
        assert goodSubsetOfBinaryMatrix(grid).equals(List.of());
    }
}
